#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        long long max_ret = 0;
        long long sum_bud = 0;
        long long sum_run = 0;
        int left = 0, right = 0;
        map<int, int> count_tree;

        int n_char = chargeTimes.size(), n_run = runningCosts.size();

        while (right < n_char)
        {
            while (right < n_char && sum_bud <= budget)
            {
                int k = right - left + 1;
                sum_run += runningCosts[right];
                count_tree[chargeTimes[right]]++;
                int max_char = (--count_tree.end())->first;

                sum_bud = max_char + k * sum_run;
                if (k > max_ret && sum_bud <= budget) max_ret = k;

                ++right;
            }

            while (left < right && sum_bud > budget)
            {

                int k = right - left;
                sum_run -= runningCosts[left];
                if (--count_tree[chargeTimes[left]] == 0)
                {
                    auto it = count_tree.find(chargeTimes[left]);
                    count_tree.erase(it);
                }
                int max_char = count_tree.empty() == true ? 0 : (--count_tree.end())->first;

                sum_bud = max_char + k * sum_run;

                ++left;
            }
        }
        return max_ret;
    }
};